// BestTimeBuyAndSellStockI.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
using namespace std;
//Best Time to Buy and Sell StockOct 30 '12

//Say you have an array for which the ith element is the price of a given stock on day i.

//If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.


//Approach
//At first glance, you might think that finding the minimum and maximum value would do, but it does have a hidden restriction, that is: You must buy before you can sell.
//Find i and j that maximizes Aj - Ai, where i < j.
int maxProfit(vector<int> &prices) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(prices.size() <=0) return 0;
	int min = 0;
	int maxDiff = 0;
	for(int i = 0; i< prices.size(); i++)
	{
		if(prices[i]< prices[min])
		{
			min = i;
		}
		int diff = prices[i]- prices[min];
		if(diff > maxDiff) 
		{
			maxDiff = diff;
		}
	}

	return maxDiff;
}

int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

